package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/find-resultant-array-after-removing-anagrams/'>移除字母异位词后的结果数组(Find Resultant Array After Removing Anagrams)</a>
 * <p>给你一个下标从 0 开始的字符串 words ，其中 words[i] 由小写英文字符组成。</p>
 * <p>
 * 在一步操作中，需要选出任一下标 i ，从 words 中 删除 words[i] 。其中下标 i 需要同时满足下述两个条件：
 *     <ol>
 *         <li>0 < i < words.length</li>
 *         <li>words[i - 1] 和 words[i] 是 字母异位词 。</li>
 *     </ol>
 *     只要可以选出满足条件的下标，就一直执行这个操作。
 * </p>
 * <p>在执行所有操作后，返回 words 。可以证明，按任意顺序为每步操作选择下标都会得到相同的结果。</p>
 * <p>字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。例如，"dacb" 是 "abdc" 的一个字母异位词。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：words = ["abba","baba","bbaa","cd","cd"]
 *      输出：["abba","cd"]
 *      解释：
 *          获取结果数组的方法之一是执行下述步骤：
 *          - 由于 words[2] = "bbaa" 和 words[1] = "baba" 是字母异位词，选择下标 2 并删除 words[2] 。
 *            现在 words = ["abba","baba","cd","cd"] 。
 *          - 由于 words[1] = "baba" 和 words[0] = "abba" 是字母异位词，选择下标 1 并删除 words[1] 。
 *            现在 words = ["abba","cd","cd"] 。
 *          - 由于 words[2] = "cd" 和 words[1] = "cd" 是字母异位词，选择下标 2 并删除 words[2] 。
 *            现在 words = ["abba","cd"] 。
 *          无法再执行任何操作，所以 ["abba","cd"] 是最终答案。
 *
 * 示例 2：
 *      输入：words = ["a","b","c","d","e"]
 *      输出：["a","b","c","d","e"]
 *      解释：
 *          words 中不存在互为字母异位词的两个相邻字符串，所以无需执行任何操作。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= words.length <= 100</li>
 *      <li>1 <= words[i].length <= 10</li>
 *      <li>words[i] 由小写英文字母组成</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/19 16:38
 */
public class LC2273FindResultantArrayAfterRemovingAnagrams_S {
    static class Solution {
        public List<String> removeAnagrams(String[] words) {
            List<String> resList = new ArrayList<>();
            String lastStringKey = "";
            for (String word : words) {
                String key = getKey(word);
                if (!key.equals(lastStringKey)) {
                    resList.add(word);
                    lastStringKey = key;
                }
            }
            return resList;
        }

        private String getKey(String str) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            return new String(chars);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListString(solution.removeAnagrams(new String[]{"abba", "baba", "bbaa", "cd", "cd"}));
        Printer.printListString(solution.removeAnagrams(new String[]{"a", "b", "c", "d", "e"}));
    }
}
